An incrementer can be thought of as an adder with only one input (A input) and a carry in signal. Accordingly, the incrementer adds by one to the A input through the carry in signal. Typically, dynamic binary incrementers are implemented utilizing a carry lookahead structure.
A N-bit binary incrementer traditionally requires 2+Log.sub.2 N stages to implement using a binary carry lookahead structure. This approach can be illustrated by the design of a 4 bit incrementer, although the technique is most useful for large bit width incrementers. A 4 bit binary incrementer has 4 data inputs A3, A2, A1, A0 and a carry input (Cin). A 4 bit binary incrementer has 4 data outputs S3, S2, S1, S0, and a carry output (Cout). In this example, S3 represents the most significant bit, S0 represents the least significant bit.
The boolean equations describing the incrementer function are shown below:
______________________________________ Cout=GP30 & Cin Group propagate (GP) S3=A3 XOR C2 S2=A2 XOR C1 S1=A1 XOR C0 S0=A0 XOR Cin where: C2=GP20 & Cin C1=GP10 & Cin C0=GP0 & Cin GP30=A3 & A2 & A1 & A0 GP20=A2 & A1 & A0 GP10=A1 & A0 GP0=A0 ______________________________________
Thus, if a 4 bit incrementer were implemented with a binary carry lookahead structure it could be constructed as shown below:
__________________________________________________________________________ Stage 1: GP32=A3&A2 GP21=A2&A1 GP10=A1&A0 C0=A0&Cin Stage 2: GP30=GP32&GP10 GP20=GP21&A0 C1=GP10&Cin Stage 3: Cout=GP30&Cin C2=GP20&Cin Stage 4: S3=A3 XOR C2 S2=A2 XOR C1 S1=A1 XOR C0 S0=A0 XOR Cin __________________________________________________________________________
Thus for a 4 bit incrementer, 2+Log.sub.2 4=4 stages of logic are required for its operation.
As can be seen from the above equations, the number of stages and the number of logic gates required to implement incrementers will increase as the number of bits in the incrementer increase. Accordingly what is needed is an incrementer which is easy to implement, and in which the number of stages required are substantially less than known dynamic incrementers. In addition, the incrementer should be easily implemented using standard logic devices. The present invention addresses such a need.